package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1997 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码，自己只理解思想
     * 经典解法，每日一看
     * @return:
     */
    class Solution {
        int mod = 1000000007;

        public int firstDayBeenInAllRooms(int[] nextVisit) {
            //dp[i][0]表示奇数次到达i时需要的天数
            //dp[i][1]表示偶数次到达i时需要的天数
            long[][] dp = new long[nextVisit.length][2];
            dp[0][1] = 1;//第二次到达0时需要一天
            for (int i = 1; i < nextVisit.length; i++) {
                //第一次到达i时,得到达两次i-1,才能达到i
                dp[i][0] = (dp[i - 1][1] + 1) % mod;
                //第二次到达i是在第一次的基础上
                // +1 到达奇数次dp[nextVisit[i]][0],此时想要再次到达i,需要先偶数次的到达i-1
                // + (dp[i - 1][1] - dp[nextVisit[i]][0]),再次到达i-1需要的天数
                //再 +1 第二次到达i
                //                              注意:这里相减可能会出现负数,所以加上mod
                dp[i][1] = (dp[i][0] + 1 + (mod + dp[i - 1][1] - dp[nextVisit[i]][0]) + 1) % mod;
            }
            return (int) dp[dp.length - 1][0];
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC1997 an = new LC1997();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
